package Leetcode第一期;

/**
 * @author : K k
 * @date : 10:16 2020/10/5
 * 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
 *
 * 示例 1:
 *
 * 输入: 1->2->3->3->4->4->5
 * 输出: 1->2->5
 * 示例 2:
 *
 * 输入: 1->1->1->2->3
 * 输出: 2->3
 */
public class 删除排序链表中的重复元素II_82 {
    //三指针
    public ListNode deleteDuplicates(ListNode head) {
        ListNode node=new ListNode(0);//哨兵
        ListNode P=node;
        ListNode L=head,R=head;
        node.next=head;
        while (R!=null){
            while (R.next!=null && R.next.val==L.val){
                R=R.next;
            }
            if (L == R) {
                //当前结点无重复
                P=L;
                R=R.next;
                L=R;
            }else {
                //有重复
                P.next=R.next;
                R.next=null;
                R=P.next;
                L=R;
            }
        }
        return node.next;
    }

    //递归
    public ListNode deleteDuplicatesA(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        if (head.val == head.next.val){
            while (head!=null && head.next!=null && head.val==head.next.val){
                head=head.next;
            }
            //若相同则抛弃相同结点，返回next
            return deleteDuplicatesA(head.next);
        }else {
            //若不同则保留当前结点
            head.next=deleteDuplicatesA(head.next);
            return head;
        }
    }
}
